//https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/description/
class DSU {
public:
    vector<int> parent;

    DSU(int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(i);
        }
    }

    int find(int x) {
        if (x != parent[x]) {
            int temp = find(parent[x]);
            parent[x] = temp;
        }
        return parent[x];
    }

    void merge(int x, int y) {
        int p_x = find(x);
        int p_y = find(y);
        if (p_x != p_y) {
            parent[p_x] = p_y;
        }
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        DSU dsu(stones.size());
        for (int i = 0; i < stones.size(); i++) {
            for (int j = i; j < stones.size(); j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    dsu.merge(i, j);
                }
            }
        }
        int cnt = stones.size();
        for (int i = 0; i < stones.size(); i++) {
            if (dsu.find(i) == i)
                cnt--;
        }
        return cnt;
    }
};
